Packet switched networks, such as the Internet, divide a message or a data stream transmitted by a source into discrete packets prior to transmission. Upon receipt of the packets by the recipient, the packets are recompiled to form the original message or data stream. As a packet-switched network, the Internet is comprised of various physical connections between computing devices, servers, routers, sub-networks, and other devices which are distributed throughout the network.
Routers connect networks, and each router has multiple inputs and multiple outputs coupled to independent network devices such as servers or other routers, the connections being made through communications links such as optical fibers or copper wires or the like.
Routers receive the packets being sent over the network and determine the next hop or segment of the network to which each packet should be sent through one of the ports of the router. When the router passes the packet to the next destination in the network, the packet is one step closer to its final destination. Each packet includes header information indicating the final destination address of the packet.
Conventionally, routers include memories and microprocessors therein for processing the packets received by the routers, as well as for performing other functions required of the router. Typically, routers contain one or more route processors, one or more forwarding engines, and a switch fabric. The route processor is a dedicated embedded subsystem which is responsible for communicating with the neighboring routers in the network to obtain current and ever-changing information about the network conditions. The route processor forms a routing table which is downloaded into and subsequently accessed for forwarding packets by the forwarding engine(s).
The forwarding engine of the router is responsible for determining the destination address and output port within the router to which to direct the received packet, this determination conventionally being made by accessing a routing table containing routing information for the entire network and performing a look-up operation.
One example of a conventional forwarding engine 10 for a router is shown in FIG. 1, wherein a plurality of general purpose CPUs 12 are provided in the architecture for the forwarding engine. Each CPU is a separate integrated circuit and receives packet data, and each CPU processes individual packets by performing a forwarding or lookup operation using an external SRAM 14 having a forwarding lookup table stored therein. As packets are received from the network, they are stored in a very large input buffer memory 16 on the front end of the forwarding engine for temporary storage until a CPU can remove a packet from the buffer and perform the forwarding/lookup operation. Such a system is commonly referred to as being “input striped,” wherein the packets are written into the input buffer memory 16 sequentially as they are received, but maybe processed in a non-sequential order as the CPUs 12 become available for processing.
Conventionally, determining the destination port within the router to which to send the received packet is a computationally intensive process, particularly in view of the high data rates of the network (known as the “line rate”), such as 10 gigabits/second. At this line rate, a forwarding engine within a router must make the destination port determination for approximately 30 million minimum-sized IP packets per second per port. Accordingly, as the router receives multiple packets, a conventional forwarding engine utilizes the large buffer memory 16 on its front end, as shown in FIG. 1, to temporarily store a number of packets until the path is determined of the packet presently being processed by the forwarding engine 10.
As such, conventional forwarding engines 10 for routers can be susceptible to performance degradation if the network traffic directed at the router is high, particularly when the router receives a plurality of packets having short lengths, thereby requiring that the look-up operations be performed quickly. Further, the increasing demand for IP-centric services over the Internet, such as voice over IP, streaming video, and data transfers to wireless devices with unique IP addresses, has increased the demand for data handling by the forwarding engines.
While conventional forwarding engines typically utilize large buffer memories 16 on their front end, such buffers can overflow during such heavy network traffic conditions, thereby requiring that the router “drop” the packet. When a packet is dropped, the packet must be resent, which degrades the overall performance of the transmission of the message. Further, such forwarding engines 10 require complex mechanisms for matching the packets stored in the input large memory buffers to the destination ports of the router.
Also, in such a conventional arrangement as shown in FIG. 1, the CPUs 12 each contend for access to the external forwarding table SRAM 14 to perform the lookup operation, which can be problematic in that contention for the external SRAM 14 can provide a bottleneck which limits the system's ability to process packets quickly. Further, if an individual CPU 12 takes longer to process a packet, during this time that individual CPU is generally not available as a resource of the forwarding engine 10 to accept new packets for processing. For at least these reasons, the conventional example shown in FIG. 1 will be problematic in handling the processing of packets at higher line rates. Further, conventional input-striped routers may experience problems with keeping packets in the proper order relative to one another.
As recognized by the present inventors, what is needed is a forwarding engine microprocessor for a router which can receive packets at a line rate and process received data packets at the line rate, thereby reducing the chance that the router will drop a new packet during continuous high traffic network activity.
It is against this background that various embodiments of the present invention were developed.